// step 1# 初始化DP数组，全部置0
int *initDP(int num) {
    int* dp = (int*)malloc(sizeof(int) * (num + 1));
    int i;
    for(i = 0; i < num + 1; ++i) {
        dp[i] = 0;
    }
    return dp;
}

// step 2# 取三个数中的最大值
int max(int num1, int num2, int num3) {
    int tempMax = num1 > num2 ? num1 : num2;
    return tempMax > num3 ? tempMax : num3;
}

// step 3# 主函数，计算整数拆分最大乘积
int integerBreak(int n){
    // step 3.1# 初始化dp数组
    int *dp = initDP(n);

    // step 3.2# 初始化基本情况，dp[2] = 1
    dp[2] = 1;

    int i;
    // step 3.3# 外层循环，从3开始遍历到n
    for(i = 3; i <= n; ++i) {
        int j;
        // step 3.3.1# 内层循环，枚举所有切分点j
        for(j = 1; j < i - 1; ++j) {
            // step 3.3.2# 更新dp[i]：取当前dp[i]，j*(i-j)，j*dp[i-j]中的最大值
            dp[i] = max(dp[i], j * (i - j), j * dp[i - j]);
        }
    }

    // step 3.4# 返回最终结果dp[n]
    return dp[n];
}
